package CheckersApplet;

import java.util.ArrayList;
import java.util.Hashtable;

public class CombinationGenerator {

	/* Prints out a combination like {1, 2} */
	private static void printc(int comb[], int k) {
		System.out.print("{");
		int i;
		for (i = 0; i < k; ++i)
			System.out.print(comb[i] + 1 + " ");
		System.out.print("}");
		System.out.println();
	}

	/*
		next_comb(int comb[], int k, int n)
			Generates the next combination of n elements as k after comb

		comb => the previous combination ( use (0, 1, 2, ..., k) for first)
		k => the size of the subsets to generate
		n => the size of the original set

		Returns: 1 if a valid combination was found
			0, otherwise
	*/
	private static int next_comb(int comb[], int k, int n) {
		int i = k - 1;
		++comb[i];
		while ((i >= 1) && (comb[i] >= n - k + 1 + i)) {
			--i;
			++comb[i];
		}

		if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
			return 0; /* No more combinations can be generated */

		/* comb now looks like (..., x, n, n, n, ..., n).
		Turn it into (..., x, x + 1, x + 2, ...) */
		for (i = i + 1; i < k; ++i)
			comb[i] = comb[i - 1] + 1;

		return 1;
	}

	public static void main(String [] args){
		int n = 21; /* The size of the set; for {1, 2, 3, 4} it's 4 */
		int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
		int[] comb = new int[k]; /* comb[i] is the index of the i-th element in the
				combination */

		/* Setup comb for the initial combination */
		int i;
		for (i = 0; i < k; ++i)
			comb[i] = i;

		/* Print the first combination */
		printc(comb, k);

		/* Generate and print all the other combinations */
		while (next_comb(comb, k, n) != 0)
			printc(comb, k);

		return;
	}
	
	public static ArrayList<PlayersPair> getPairCombinations(int n){
		ArrayList<PlayersPair> ret = new ArrayList<PlayersPair>();
		int[] comb = new int[2];
		
		comb[0] = 0;
		comb[1] = 1;

		ret.add(new PlayersPair(comb[0], comb[1]));
		while (next_comb(comb, 2, n) != 0)
			ret.add(new PlayersPair(comb[0], comb[1]));;
		
//		for (int i = 0; i < ret.size(); i++)		{
//			System.out.print("{");
//			System.out.print(ret.get(i).getFirst() + " " + ret.get(i).getSecond());
//			System.out.print("}");
//			System.out.println();
//		}
		
		return ret;
	}
}
